#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,k;
		int flag = 0;
		scanf("%d %d",&n,&k);
		for(int i = 2;i*i<=n;i++)
		{
			if(n%i==0)
			{
				flag = i;
				break;
			}
		}
		if(!flag) flag = n;
		if((flag+n)%2==0)
		{
			n += flag;
			k--;
			flag = 2;
			
		}
		//printf("***%d %d\n",n,flag);
		printf("%d\n",n+flag*k); 
	}
} 
